Combination sum

Time: O(KxN^K); Space: O(K); medium

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Notes:

  • All numbers (including target) will be positive integers.

  • Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak)

  • Different combinations can be in any order.

  • The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7

Output:

[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8

Output:

[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

[1]:

class Solution1(object):
    """
    Time: O(K*N^K)
    Space: O(K)
    """
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        self.combinationSumRecu(sorted(candidates), result, 0, [], target)
        return result

    def combinationSumRecu(self, candidates, result, start, intermediate, target):
        if target == 0:
            result.append(list(intermediate))

        while start < len(candidates) and candidates[start] <= target:
            intermediate.append(candidates[start])
            self.combinationSumRecu(candidates, result, start, intermediate, target - candidates[start])
            intermediate.pop()
            start += 1

[4]:

s = Solution1()

candidates = [2,3,6,7]
target = 7
assert s.combinationSum(candidates, target) == [[7], [2,2,3]] or [[2,2,3], [7]]

candidates = [2,3,5]
target = 8
assert s.combinationSum(candidates, target) == [
  [2,2,2,2],
  [2,3,3],
  [3,5]
]